/**
 * 240. Search a 2d Matrix II 搜索二维矩阵 II
 * https://leetcode.com/problems/search-a-2d-matrix-ii/
 */
class SearchA2dMatrixII {
    /**
     * 方法：从矩阵右上角开始搜索，利用矩阵排序特性进行剪枝
     * 
     * Args:
     *     matrix: int[][], 二维整数矩阵，每行每列都按升序排列
     *     target: int, 要搜索的目标值
     * 
     * Returns:
     *     boolean, 如果找到目标值返回true，否则返回false
     * 
     * Time: O(m + n), 最坏情况下需要遍历矩阵的一行和一列
     * Space: O(1), 只使用了常数级别的额外空间
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n-1; // 从右上角开始
        while(i < m && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }
            if(matrix[i][j] < target){
                i++;  // 向下移动
            }else{
                j--;  // 向左移动
            }
        }
        return false;
    }
}